/** @file Graph.java
 *
 *  @author Jon Turner
 *  @date 2011
 *  This is open source software licensed under the Apache 2.0 license.
 *  See http://www.apache.org/licenses/LICENSE-2.0 for details.
 */

package algoLib.dataStructures.graphs;
import algoLib.dataStructures.basic.*;

/** Data structure for undirected graph.
 *
 *  Graph size (number of vertices and max number of edges) must
 *  be specified when a Graph object is instantiated.
 *  Edges can be added and removed from the graph.
 *  Methods are provided to facilitate graph traversal,
 *  either by iterating through all edges of the graph
 *  or all edges incident to a specific vertex.
 */
public class Graph {

	protected int N;		///< number of vertices 
	protected int M;		///< number of edges
	protected int maxEdge;		///< max number of edges

	private int[] fe;		///< fe[v] is first edge incident to v

	private class EdgeInfo {
	int	l;			///< l is left endpoint of edge
	int	r;			///< r is right endpoint of edge
	};
	EdgeInfo[] evec;		///< array of edge structures
	private UiSetPair edges;	///< sets of in-use and free edges
	private UiClist adjLists;	///< collection of edge adjacency lists
					///< stores edge e as both 2e and 2e+1

	/** Construct Graph with space for a specified # of vertices and edges.
	 *  @param N1 is number of vertices in the graph
	 *  @param maxEdge1 is the maximum number of edges
	 */
	public Graph(int N, int maxEdge) {
		assert(N > 0 && maxEdge > 0);
		this.N = N; this.maxEdge = maxEdge; M = 0;
		fe = new int[N+1];
		evec = new EdgeInfo[maxEdge+1];
		edges = new UiSetPair(maxEdge);
		adjLists = new UiClist(2*maxEdge+1);
		for (int u = 1; u <= N; u++) fe[u] = 0;
		for (int e = 0; e <= maxEdge; e++) evec[e] = null;
	}

	/** Get the number of vertices.
	 *  @return the number of vertices in the graph.
	 */
	public int n() { return N; }
	
	/** Get the number of edges.
	 *  @return the number of edges in the graph.
	 */
	public int m() { return M; }
	
	/** Determine if an edge number corresponds to a valid edge.
	 *  @param e is the edge number to be verified
	 *  @return true if e is a valid edge number, else false.
	 */
	public boolean validEdge(int e) { return edges.isIn(e); }
	
	/** Get the first edge in the overall list of edges.
	 *  @return the first edge in the list
	 */
	public int first() { return edges.firstIn(); }
	
	/** Get the next edge in the overall list of edges.
	 *  @param e is the edge whose successor is requested
	 *  @return the next edge in the list, or 0 if e is not in the list
	 *  or it has no successor
	 */
	public int next(int e) { return edges.nextIn(e); }
	
	/** Get the first edge incident to a vertex.
	 *  @param v is the the vertex of interest
	 *  @return the first edge incident to v
	 */
	public int firstAt(int v) { 
		assert(1 <= v && v <= N); return fe[v]/2;
	}
	
	/** Get the next edge in the adjacency list for a specific vertex.
	 *  @param v is the edge whose adjacency list we're accessing
	 *  @param e is the edge whose successor is requested
	 *  @return the next edge in the adjacency list for v
	 *  or 0 if e is not incident to v or is the last edge on the list
	 */
	public int nextAt(int v, int e) {
		assert(1 <= v && v <= N && 1 <= e && e <= maxEdge);
		if (v != evec[e].l && v != evec[e].r) return 0;
		int ee = (v == evec[e].l ? 2*e : 2*e+1);
		int ff = adjLists.suc(ee);
		return (fe[v] == ff ? 0 : ff/2);
	}
	
	/** Get the left endpoint of an edge.
	 *  @param e is the edge of interest
	 *  @return the left endpoint of e, or 0 if e is not a valid edge.
	 */
	public int left(int e) {
		assert(0 <= e && e <= maxEdge);
		return evec[e].l;
	}
	
	/** Get the right endpoint of an edge.
	 *  @param e is the edge of interest
	 *  @return the right endpoint of e, or 0 if e is not a valid edge.
	 */
	public int right(int e) {
		assert(0 <= e && e <= maxEdge);
		return (evec[e].l == 0 ? 0 : evec[e].r);
	}
	
	/** Get the other endpoint of an edge.
	 *  @param v is a vertex
	 *  @param e is an edge incident to v
	 *  @return the other vertex incident to e, or 0 if e is not 
	 *  a valid edge  or it is not incident to v.
	 */
	// Return other endpoint of e.
	public int mate(int v, int e) {
		assert(1 <= v && v <= N && 1 <= e && e <= maxEdge);
		return (evec[e].l == 0 ?
			0 : (v == evec[e].l ?
			     evec[e].r : (v == evec[e].r ? evec[e].l : 0)));
	}
	
	/** Join two vertices with an edge.
	 *  @param u is the left endpoint for the new edge
	 *  @param v is the right endpoint for the new edge
	 *  @return the edge number for the new edge or 0
	 *  on failure
	 */
	public int join(int u, int v) {
		assert(1 <= u && u <= N && 1 <= v && v <= N);
	
		int e = edges.firstOut();
		if (e == 0) return 0;
		edges.swap(e);

		if (evec[e] == null) evec[e] = new EdgeInfo();
	
		// initialize edge information
		evec[e].l = u; evec[e].r = v;
	
		// add edge to the adjacency lists
		// in the adjLists data structure, each edge appears twice,
		// as 2*e and 2*e+1
		if (fe[u] != 0) adjLists.join(2*e,fe[u]);
		if (fe[v] != 0) adjLists.join(2*e+1,fe[v]);
		if (fe[u] == 0) fe[u] = 2*e;
		if (fe[v] == 0) fe[v] = 2*e+1;
	
		M++;
	
		return e;
	}
	
	/** Remove an edge from the graph.
	 *  @param e is the edge to be removed.
	 *  @return true on success, false on failure
	 */
	public boolean remove(int e) {
		assert(1 <= e && e <= maxEdge);
		if (edges.isOut(e)) return false;
		edges.swap(e);
	
		int u = evec[e].l;
		if (fe[u] == 2*e)
			fe[u] = (adjLists.suc(2*e) == 2*e ?
				 0 :adjLists.suc(2*e));
		u = evec[e].r;
		if (fe[u] == 2*e+1)
			fe[u] = (adjLists.suc(2*e+1) == 2*e+1 ?
					0 : adjLists.suc(2*e+1));
	
		adjLists.remove(2*e); adjLists.remove(2*e+1);
	
		evec[e].l = 0;
	
		M--;
		return true;
	}
	
	/** Construct a String representation of the Graph object.
	 *  For small graphs (at most 26 vertices), vertices are
	 *  represented in the String as lower case letters.
	 *  For larger graphs, vertices are represented by integers.
	 *  @param s is a String object provided by the caller which
	 *  is modified to provide a representation of the Graph.
	 *  @return a reference to the String
	 */
	public String toString() {
		String s = "";
		for (int u = 1; u <= n(); u++) {
			if (firstAt(u) == 0) continue;
			for (int e = firstAt(u); e != 0; e = nextAt(u,e)) {
				s += "(";
				if (n() <= 26)
					s += ((char) ('a'+(u-1))) + ","
					     + ((char) ('a'+(mate(u,e)-1)));
				else 
					s += u + "," + mate(u,e);
				s += ")"; if (nextAt(u,e) != 0) s += " ";
			}
			s += "\n";
		}
		return s;
	}
}
